﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Problem14
{
    class Program
    {
        static Dictionary<long, long> master = new Dictionary<long, long>(10000000);

        static void Main(string[] args)
        {
            for (int num = 1000000 - 1; num >= 1; num--)
            {
                long chainLength = GetChainLength(num);
            }

            long maxChain = 0;
            long maxNumber = 1;
            foreach (var pair in master)
            {
                if (pair.Key < 1000000 && pair.Value > maxChain)
                {
                    maxChain = pair.Value;
                    maxNumber = pair.Key;
                }
            }

            Console.WriteLine(maxNumber);
            Console.ReadKey();
        }

        private static long GetChainLength(long num)
        {
            if (master.ContainsKey(num)) return master[num];
            if (num <= 1) return 1;

            if (num % 2 == 0)
            {
                master.Add(num, 1 + GetChainLength(num / 2));
            }
            else
            {
                master.Add(num, 1 + GetChainLength(3 * num + 1));
            }

            return master[num];
        }
    }
}
